/*************************************************************************
 * File Name:    Substring_with_Concatenation_of_All_words.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/16 17:47:03
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Substring with Concatenation of All Words
 |
 | You are given a string, S, and a list of words, L, that are all of the same length.
 | Find all starting indices of substring(s) in S that is a concatenation of each word
 | in L exactly once and without any intervening characters.
 |
 | For example, given:
 | S: "barfoothefoobarman"
 | L: ["foo", "bar"]
 |
 | You should return the indices: [0,9].
 | (order does not matter).
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L)
    {
        if (L.size() == 0) return vector<int>();
        
        map<string, int> dict;
        int m = S.size();
        int n = L.size();
        int len = L[0].size();
        int i, j;
        
        for (i = 0; i < n; ++i) ++dict[L[i]];
        
        map<string, int> cnt;
        string sub;
        vector<int> ans;
        for (i = 0; i <= m - n * len; ++i) {
            cnt.clear();
            for (j = 0; j < n; ++j) {
                sub = S.substr(i + j * len, len);
                if (dict.find(sub) == dict.end()) break;
                ++cnt[sub];
                if (cnt[sub] > dict[sub]) break;
            }
            if (j >= n) ans.push_back(i);
        }
        return ans;
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;
    //string S = "a";
    string S = "acaacc";
    vector<string> L;

    //L.push_back("a");
    L.push_back("ca");
    L.push_back("ac");

    vector<int> ans = sol.findSubstring(S, L);

    for (size_t i = 0; i < ans.size(); ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}
